//binary_tree.cpp
//inorder traversal 
//Node without parent
//successor function
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
struct Node{
public:
  char* name;
  Node* left;
  Node* right;
  Node(string n = "empty string");
  ~Node(){free(name);}
};
Node::Node(string n)
{
  name = (char*)malloc(n.length()+1);
  const char * tmp = n.c_str();
  strcpy(name,tmp);
}
Node n0("node 0");
Node n1("node 1");
Node n2("node 2");
Node n3("node 3");
Node n4("node 4");
Node n5("node 5");
Node n6("node 6");
Node n7("node 7");
Node n8("node 8");
Node n9("node 9");

Node* make_tree(void)
{
  n0.left = &n1;
  n0.right = &n2;

  n1.left = &n3;
  n1.right = &n4;

  n3.left = &n5;
  n3.right = &n6;

  n4.right = &n8;

  n6.right = &n7;
  n8.left = &n9;
  
  return &n0;
}

void inorder_traversal(Node* root)
{
  if(root){
    inorder_traversal(root->left);
    printf("%s\t",root->name);
    inorder_traversal(root->right);
  }
  return;
}
class Tree_iterator{
  stack<Node*> ancestor;
  Node* current;
public:
  Tree_iterator(Node* root = NULL);
  char* next();
  Node* go_leftdown();
  Node* go_leftup();
};

Tree_iterator::Tree_iterator(Node* root)
{
  current = root;
  go_leftdown();
}
Node* Tree_iterator::go_leftdown()
{
  while(current->left){
    ancestor.push(current);
    current = current->left;
  }
  return current;
}
Node* Tree_iterator::go_leftup()
{
  while(ancestor.size()!=0&&ancestor.top()->right==current){
    current = ancestor.top();
    ancestor.pop();
  }
  return current;
}

char* Tree_iterator::next()
{
  if(current == NULL){
    printf("Reach the end\n");
    return NULL;
  }
  char* val = current->name;
  if(current->right){
    ancestor.push(current);
    current=current->right;
    go_leftdown();
  }
  else{
    go_leftup();
    if(ancestor.size() != 0){
      current = ancestor.top();
      ancestor.pop();
    }
    else{
      current = NULL;//reach the end
    }
  }
  return val;
}


int main(int argc, char *argv[])
{
  Node* root = make_tree();
  inorder_traversal(root);
  printf("\n");
  Tree_iterator iter(root);
  for(char * name=iter.next();name!=NULL;name=iter.next()){
    printf("%s\t",name);
  }
  printf("\n");
}


